UVA437「The Tower of Babylon」

1. 题目

Description

Perhaps you have heard of the legend of the Tower of Babylon. Nowadays many details of this tale have been forgotten. So now, in line with the educational nature of this contest, we will tell you the whole story:

The babylonians had $n$ types of blocks, and an unlimited supply of blocks of each type. Each type- $i$ block was a rectangular solid with linear dimensions ( $x_i$ , $y_i$ , $z_i$ ). A block could be reoriented so that any two of its three dimensions determined the dimensions of the base and the other dimension was the height.

They wanted to construct the tallest tower possible by stacking blocks. The problem was that, in building a tower, one block could only be placed on top of another block as long as the two base dimensions of the upper block were both strictly smaller than the corresponding base dimensions of the lower block. This meant, for example, that blocks oriented to have equal-sized bases couldn’t be stacked.

Your job is to write a program that determines the height of the tallest tower the babylonians can build with a given set of blocks.

Input

The input file will contain one or more test cases. The first line of each test case contains an integer $n$ , representing the number of different blocks in the following data set. The maximum value for $n$ is $30$ .

Each of the next $n$ lines contains three integers representing the values $x_i$ , $y_i$ and $z_i$ .

Input is terminated by a value of zero ( $0$ ) for $n$ .

Output

For each test case, print one line containing the case number (they are numbered sequentially starting from $1$ ) and the height of the tallest possible tower in the format：
Case $case: maximum height = $height

Sample Input

Sample Output

Case 1: maximum height = 40
Case 2: maximum height = 21
Case 3: maximum height = 28
Case 4: maximum height = 342

2. 题解

分析

显然这是一道 dp 题，因为每个块可以以给出的三条棱中的任意一条作为高，我们不妨将一个块按照高度取不同的棱分为三个块（即将原来的无向块变成有向块）。其次我们注意到，虽然每种有向块都有无穷多个，但是其实一种有向块最多只有一个会出现在塔中（因为要求块底部长宽从下到上严格递增），这样问题就等价于给出 $3n$ 个有向块，求塔的最大高度。如何构造状态以及状态转移方程是重点。定义有向块数组 $rect$ ，其字段 $l,w,h$ 分别表示有向块的长、宽、高。这里我们考虑顺序遍历所有有向块进行动态规划，则需要将一个有向块的长、宽分别定义为有向块底面 $l,w$ 中的较大值和较小值，然后根据先长后宽由大到小对有向块进行排序，这样才能保证最终塔高的最大值一定在顺序遍历有向块过程中出现（因为最终塔一定满足从底块到顶块按长、宽严格递减的条件，而满足这种条件的所有可能塔的构造都在顺序遍历有向块时出现）。构造的状态及状态转移方程如下：

首先构造状态 $dp[i][j]$ 表示遍历完第 $i$ 个块后，塔顶为第 $j$ 个块时塔还能获得的最大高度。
然后构造状态转移方程

$\begin{array}{c} dp[i][j] = \begin{cases} max(dp[i+1][j], dp[i+1][i+1]+rect[i+1].h) & if \ \ rect[j].l \gt rect[i+1].l \ \&\& \ rect[j].w \gt rect[i+1].w \\ dp[i+1][j] & others \end{cases} \end{array}$

最终答案即为 $dp[0][0]$ 。

代码

#include <bits/stdc++.h>
#define ll int
#define MAXN 105
#define INF 0x3f3f3f3f
using namespace std;

// 有向块
ll cnt;
struct Rect {
    ll l, w, h;
    bool operator < (const Rect r) const {
        return l == r.l ? w > r.w : l > r.l;
    }
}rect[MAXN];
// 将无向块转为三个有向块
// 并设定块长度大于等于宽度
void addRect(ll a, ll b, ll c) {
    ++cnt, rect[cnt].l = max(a,b), rect[cnt].w = min(a,b), rect[cnt].h = c;
    ++cnt, rect[cnt].l = max(b,c), rect[cnt].w = min(b,c), rect[cnt].h = a;
    ++cnt, rect[cnt].l = max(c,a), rect[cnt].w = min(c,a), rect[cnt].h = b;
}

int main()
{
    ll n;
    ll t = 1;
    while(true) {
        scanf("%d", &n);
        if(n == 0)  break;
        cnt = 0;
        for(ll i = 0; i < n; ++i) {
            ll a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            addRect(a, b, c);
        }
        // 对有向块排序
        sort(rect+1, rect+cnt+1);
        // 初始第 0 块为底面
        rect[0].l = INF, rect[0].w = INF, rect[0].h = INF;
        // 假定最后一块为一个点
        ++cnt, rect[cnt].l = 0, rect[cnt].w = 0, rect[cnt].h = 0;
        ll dp[MAXN][MAXN] = {0};
        for(ll i = cnt-1; ~i; --i) {
            for(ll j = i; ~j; --j) {
                dp[i][j] = dp[i+1][j];
                if(rect[j].l > rect[i+1].l && rect[j].w > rect[i+1].w) {
                    dp[i][j] = max(dp[i][j], dp[i+1][i+1]+rect[i+1].h);
                }
            }
        }
        printf("Case %d: maximum height = %d\n", t++, dp[0][0]);
    }
    return 0;
}